/*
 * Copyright 2011 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Bitcoin.Cryptography;

namespace Bitcoin
{
    /// <summary>
    ///     A custom form of base58 is used to encode BitCoin addresses. Note that this is not the same base58 as used by
    ///     Flickr, which you may see reference to around the internet.
    /// </summary>
    /// <remarks>
    ///     Satoshi says: why base-58 instead of standard base-64 encoding?<p />
    ///     <ul>
    ///         <li>
    ///             Don't want 0OIl characters that look the same in some fonts and
    ///             could be used to create visually identical looking account numbers.
    ///         </li>
    ///         <li>A string with non-alphanumeric characters is not as easily accepted as an account number.</li>
    ///         <li>E-mail usually won't line-break if there's no punctuation to break at.</li>
    ///         <li>Double clicking selects the whole number as one word if it's all alphanumeric.</li>
    ///     </ul>
    /// </remarks>
    public static class Base58
    {
        private const string _alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
        private static readonly BigInteger _base = new BigInteger(58);
        private static readonly BigInteger _zero = new BigInteger(0);

        /// <exception cref="AddressFormatException" />
        public static byte[] Decode(string input)
        {
            var bytes = DecodeToBigInteger(input).ToByteArray();
            bytes = bytes.Reverse().ToArray();
            // We may have got one more byte than we wanted, if the high bit of the next-to-last byte was not zero. This
            // is because BigIntegers are represented with twos-compliment notation, thus if the high bit of the last
            // byte happens to be 1 another 8 zero bits will be added to ensure the number parses as positive. Detect
            // that case here and chop it off.
            //var stripSignByte = bytes.Length > 1 && bytes[0] == 0 && bytes[1] >= 0x80;
            var stripSignByte = bytes.Length > 0 && bytes[0] == 0;

            // Count the leading zeros, if any.
            var leadingZeros = 0;
            for (var i = 0; i < input.Length && input[i] == _alphabet[0]; i++)
            {
                leadingZeros++;
            }
            // Now cut/pad correctly. Java 6 has a convenience for this, but Android can't use it.
            var tmp = new byte[bytes.Length - (stripSignByte ? 1 : 0) + leadingZeros];
            Array.Copy(bytes, stripSignByte ? 1 : 0, tmp, leadingZeros, tmp.Length - leadingZeros);
            return tmp;
        }

        /// <summary>
        ///     Uses the checksum in the last 4 bytes of the decoded data to verify the rest are correct. The checksum is
        ///     removed from the returned data.
        /// </summary>
        /// <exception cref="AddressFormatException">If the input is not base 58 or the checksum does not validate.</exception>
        public static byte[] DecodeChecked(string input)
        {
            var tmp = Decode(input);
            if (tmp.Length < 4)
                throw new AddressFormatException("Input too short");
            var checksum = new byte[4];
            Array.Copy(tmp, tmp.Length - 4, checksum, 0, 4);
            var bytes = new byte[tmp.Length - 4];
            Array.Copy(tmp, 0, bytes, 0, tmp.Length - 4);
            tmp = SecurityUtility.DoubleDigest(bytes);
            var hash = new byte[4];
            Array.Copy(tmp, 0, hash, 0, 4);
            if (!hash.SequenceEqual(checksum))
            {
                throw new AddressFormatException("Checksum does not validate");
            }
            return bytes;
        }

        /// <exception cref="AddressFormatException" />
        public static BigInteger DecodeToBigInteger(string input)
        {
            var bi = _zero;
            // Work backwards through the string.
            for (var i = input.Length - 1; i >= 0; i--)
            {
                var alphaIndex = _alphabet.IndexOf(input[i]);
                if (alphaIndex == -1)
                {
                    throw new AddressFormatException("Illegal character " + input[i] + " at " + i);
                }
                var alphaValue = new BigInteger(alphaIndex);
                var multiplier = BigInteger.Pow(_base, input.Length - 1 - i);
                bi = bi + (alphaValue*multiplier);
            }
            return bi;
        }

        public static string Encode(byte[] input)
        {
            // TODO: This could be a lot more efficient.

            // Convert big endian data to little endian
            // Extra zero at the end make sure bignum will interpret as a positive number
            var temp = input.Reverse().Concat(new byte[] {0x0});

            // BouncyCastle BigInteger is big endian
            //var temp = (new byte[] { 0x0 }).Concat(input);

            // Convert little endian data to bignum
            var bn = new BigInteger(temp.ToArray());

            // Expected size increase from base58 conversion is approximately 137%
            // use 138% to be safe
            var expectedLength = input.Length*138/100 + 1;

            // Convert bignum to string
            var str = new List<char>(expectedLength);

            BigInteger rem;
            BigInteger div;
            //int safety = 0;
            while (bn > _zero)
            {
                div = BigInteger.DivRem(bn, _base, out rem);
                //if (safety++ > 100000) throw new Exception();
                //var divide = bn.DivideAndRemainder(_base);
                //var mod = bn.Mod(_base);
                //var mod = divide[1];
                //bn = bn.Subtract(mod).Divide(_base);
                //bn = divide[0];
                //str.Insert(0, _alphabet[mod.IntValue]);
                //str.Add(_alphabet[mod.IntValue]);
                str.Add(_alphabet[(int) rem]);
                bn = div;
            }

            // Convert leading zeros too.
            foreach (var anInput in input)
            {
                if (anInput == 0)
                {
                    str.Add(_alphabet[0]);
                    //str.Insert(0, _alphabet[0]);
                }
                else
                {
                    break;
                }
            }
            //return new String(str.ToArray());

            // Convert little endian string to big endian
            var result = new String(str.AsEnumerable().Reverse().ToArray());
            return result;
        }

        /// <summary>
        ///     Encode a byte vector to a base58-encoded string, including checksum
        /// </summary>
        public static string EncodeChecked(byte[] bytes)
        {
            var check = SecurityUtility.DoubleDigest(bytes, 0, bytes.Length);
            var tmp = new byte[bytes.Length + 4];
            Array.Copy(bytes, tmp, bytes.Length);
            Array.Copy(check, 0, tmp, bytes.Length, 4);
            return Base58.Encode(tmp);
        }
    }
}